Loading…
Full rainbow matchings in graphs and hypergraphs
Let G be a simple graph that is properly edge-coloured with m colours and let \[\mathcal{M} = \{ {M_1},...,{M_m}\} \] be the set of m matchings induced by the colours in G . Suppose that \[m \leqslant n - {n^c}\] , where \[c > 9/10\] , and every matching in \[\mathcal{M}\] has size n . Then G con...
Saved in:
| Published in: | Combinatorics, probability & computing probability & computing, 2021-09, Vol.30 (5), p.762-780 |
|---|---|
| Main Authors: | , , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c273t-b81d93cb0b5abc534c15d5c04f4028ce8333db7d252a81d08970bdaf47f960cd3 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c273t-b81d93cb0b5abc534c15d5c04f4028ce8333db7d252a81d08970bdaf47f960cd3 |
| container_end_page | 780 |
| container_issue | 5 |
| container_start_page | 762 |
| container_title | Combinatorics, probability & computing |
| container_volume | 30 |
| creator | Gao, Pu Ramadurai, Reshma Wanless, Ian M. Wormald, Nick |
| description | Let
G
be a simple graph that is properly edge-coloured with
m
colours and let
\[\mathcal{M} = \{ {M_1},...,{M_m}\} \]
be the set of
m
matchings induced by the colours in
G
. Suppose that
\[m \leqslant n - {n^c}\]
, where
\[c > 9/10\]
, and every matching in
\[\mathcal{M}\]
has size
n
. Then
G
contains a full rainbow matching,
i.e.
a matching that contains exactly one edge from
M
i
for each
\[1 \leqslant i \leqslant m\]
. This answers an open problem of Pokrovskiy and gives an affirmative answer to a generalization of a special case of a conjecture of Aharoni and Berger. Related results are also found for multigraphs with edges of bounded multiplicity, and for hypergraphs.
Finally, we provide counterexamples to several conjectures on full rainbow matchings made by Aharoni and Berger. |
| doi_str_mv | 10.1017/S0963548320000620 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2577678724</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2577678724</sourcerecordid><originalsourceid>FETCH-LOGICAL-c273t-b81d93cb0b5abc534c15d5c04f4028ce8333db7d252a81d08970bdaf47f960cd3</originalsourceid><addsrcrecordid>eNplkEtLw0AUhQdRMFZ_gLsB19E778lSirVCwYW6HuaRNClpEmdSpP_ehLjzbg6X83EOHITuCTwSIOrpAwrJBNeMwnSSwgXKCJdFTolklyib7Xz2r9FNSoeJEUJChmBzalscbdO5_gcf7ejrptsn3HR4H-1QJ2y7gOvzUMblv0VXlW1TefenK_S1eflcb_Pd--vb-nmXe6rYmDtNQsG8Ayes84JxT0QQHnjFgWpfasZYcCpQQe2Egi4UuGArrqpCgg9shR6W3CH236cyjebQn2I3VRoqlJJKK8oniiyUj31KsazMEJujjWdDwMzDmH_DsF-xEVRs</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2577678724</pqid></control><display><type>article</type><title>Full rainbow matchings in graphs and hypergraphs</title><source>Cambridge University Press</source><creator>Gao, Pu ; Ramadurai, Reshma ; Wanless, Ian M. ; Wormald, Nick</creator><creatorcontrib>Gao, Pu ; Ramadurai, Reshma ; Wanless, Ian M. ; Wormald, Nick</creatorcontrib><description>Let
G
be a simple graph that is properly edge-coloured with
m
colours and let
\[\mathcal{M} = \{ {M_1},...,{M_m}\} \]
be the set of
m
matchings induced by the colours in
G
. Suppose that
\[m \leqslant n - {n^c}\]
, where
\[c > 9/10\]
, and every matching in
\[\mathcal{M}\]
has size
n
. Then
G
contains a full rainbow matching,
i.e.
a matching that contains exactly one edge from
M
i
for each
\[1 \leqslant i \leqslant m\]
. This answers an open problem of Pokrovskiy and gives an affirmative answer to a generalization of a special case of a conjecture of Aharoni and Berger. Related results are also found for multigraphs with edges of bounded multiplicity, and for hypergraphs.
Finally, we provide counterexamples to several conjectures on full rainbow matchings made by Aharoni and Berger.</description><identifier>ISSN: 0963-5483</identifier><identifier>EISSN: 1469-2163</identifier><identifier>DOI: 10.1017/S0963548320000620</identifier><language>eng</language><publisher>Cambridge: Cambridge University Press</publisher><subject>Combinatorics ; Graph coloring ; Graph theory ; Graphs ; Matching</subject><ispartof>Combinatorics, probability & computing, 2021-09, Vol.30 (5), p.762-780</ispartof><rights>The Author(s), 2021. Published by Cambridge University Press</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c273t-b81d93cb0b5abc534c15d5c04f4028ce8333db7d252a81d08970bdaf47f960cd3</citedby><cites>FETCH-LOGICAL-c273t-b81d93cb0b5abc534c15d5c04f4028ce8333db7d252a81d08970bdaf47f960cd3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27901,27902</link.rule.ids></links><search><creatorcontrib>Gao, Pu</creatorcontrib><creatorcontrib>Ramadurai, Reshma</creatorcontrib><creatorcontrib>Wanless, Ian M.</creatorcontrib><creatorcontrib>Wormald, Nick</creatorcontrib><title>Full rainbow matchings in graphs and hypergraphs</title><title>Combinatorics, probability & computing</title><description>Let
G
be a simple graph that is properly edge-coloured with
m
colours and let
\[\mathcal{M} = \{ {M_1},...,{M_m}\} \]
be the set of
m
matchings induced by the colours in
G
. Suppose that
\[m \leqslant n - {n^c}\]
, where
\[c > 9/10\]
, and every matching in
\[\mathcal{M}\]
has size
n
. Then
G
contains a full rainbow matching,
i.e.
a matching that contains exactly one edge from
M
i
for each
\[1 \leqslant i \leqslant m\]
. This answers an open problem of Pokrovskiy and gives an affirmative answer to a generalization of a special case of a conjecture of Aharoni and Berger. Related results are also found for multigraphs with edges of bounded multiplicity, and for hypergraphs.
Finally, we provide counterexamples to several conjectures on full rainbow matchings made by Aharoni and Berger.</description><subject>Combinatorics</subject><subject>Graph coloring</subject><subject>Graph theory</subject><subject>Graphs</subject><subject>Matching</subject><issn>0963-5483</issn><issn>1469-2163</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2021</creationdate><recordtype>article</recordtype><recordid>eNplkEtLw0AUhQdRMFZ_gLsB19E778lSirVCwYW6HuaRNClpEmdSpP_ehLjzbg6X83EOHITuCTwSIOrpAwrJBNeMwnSSwgXKCJdFTolklyib7Xz2r9FNSoeJEUJChmBzalscbdO5_gcf7ejrptsn3HR4H-1QJ2y7gOvzUMblv0VXlW1TefenK_S1eflcb_Pd--vb-nmXe6rYmDtNQsG8Ayes84JxT0QQHnjFgWpfasZYcCpQQe2Egi4UuGArrqpCgg9shR6W3CH236cyjebQn2I3VRoqlJJKK8oniiyUj31KsazMEJujjWdDwMzDmH_DsF-xEVRs</recordid><startdate>20210901</startdate><enddate>20210901</enddate><creator>Gao, Pu</creator><creator>Ramadurai, Reshma</creator><creator>Wanless, Ian M.</creator><creator>Wormald, Nick</creator><general>Cambridge University Press</general><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7SC</scope><scope>7XB</scope><scope>8AL</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K7-</scope><scope>L6V</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0N</scope><scope>M7S</scope><scope>P5Z</scope><scope>P62</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PTHSS</scope><scope>Q9U</scope></search><sort><creationdate>20210901</creationdate><title>Full rainbow matchings in graphs and hypergraphs</title><author>Gao, Pu ; Ramadurai, Reshma ; Wanless, Ian M. ; Wormald, Nick</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c273t-b81d93cb0b5abc534c15d5c04f4028ce8333db7d252a81d08970bdaf47f960cd3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2021</creationdate><topic>Combinatorics</topic><topic>Graph coloring</topic><topic>Graph theory</topic><topic>Graphs</topic><topic>Matching</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Gao, Pu</creatorcontrib><creatorcontrib>Ramadurai, Reshma</creatorcontrib><creatorcontrib>Wanless, Ian M.</creatorcontrib><creatorcontrib>Wormald, Nick</creatorcontrib><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>Computing Database (Alumni Edition)</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>Materials Science & Engineering Database (Proquest)</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central UK/Ireland</collection><collection>Advanced Technologies & Aerospace Database (1962 - current)</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>Computer Science Database</collection><collection>ProQuest Engineering Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>Computing Database</collection><collection>ProQuest Engineering Database</collection><collection>ProQuest advanced technologies & aerospace journals</collection><collection>ProQuest Advanced Technologies & Aerospace Collection</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>Engineering collection</collection><collection>ProQuest Central Basic</collection><jtitle>Combinatorics, probability & computing</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Gao, Pu</au><au>Ramadurai, Reshma</au><au>Wanless, Ian M.</au><au>Wormald, Nick</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Full rainbow matchings in graphs and hypergraphs</atitle><jtitle>Combinatorics, probability & computing</jtitle><date>2021-09-01</date><risdate>2021</risdate><volume>30</volume><issue>5</issue><spage>762</spage><epage>780</epage><pages>762-780</pages><issn>0963-5483</issn><eissn>1469-2163</eissn><abstract>Let
G
be a simple graph that is properly edge-coloured with
m
colours and let
\[\mathcal{M} = \{ {M_1},...,{M_m}\} \]
be the set of
m
matchings induced by the colours in
G
. Suppose that
\[m \leqslant n - {n^c}\]
, where
\[c > 9/10\]
, and every matching in
\[\mathcal{M}\]
has size
n
. Then
G
contains a full rainbow matching,
i.e.
a matching that contains exactly one edge from
M
i
for each
\[1 \leqslant i \leqslant m\]
. This answers an open problem of Pokrovskiy and gives an affirmative answer to a generalization of a special case of a conjecture of Aharoni and Berger. Related results are also found for multigraphs with edges of bounded multiplicity, and for hypergraphs.
Finally, we provide counterexamples to several conjectures on full rainbow matchings made by Aharoni and Berger.</abstract><cop>Cambridge</cop><pub>Cambridge University Press</pub><doi>10.1017/S0963548320000620</doi><tpages>19</tpages></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0963-5483 |
| ispartof | Combinatorics, probability & computing, 2021-09, Vol.30 (5), p.762-780 |
| issn | 0963-5483 1469-2163 |
| language | eng |
| recordid | cdi_proquest_journals_2577678724 |
| source | Cambridge University Press |
| subjects | Combinatorics Graph coloring Graph theory Graphs Matching |
| title | Full rainbow matchings in graphs and hypergraphs |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-14T19%3A36%3A55IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Full%20rainbow%20matchings%20in%20graphs%20and%20hypergraphs&rft.jtitle=Combinatorics,%20probability%20&%20computing&rft.au=Gao,%20Pu&rft.date=2021-09-01&rft.volume=30&rft.issue=5&rft.spage=762&rft.epage=780&rft.pages=762-780&rft.issn=0963-5483&rft.eissn=1469-2163&rft_id=info:doi/10.1017/S0963548320000620&rft_dat=%3Cproquest_cross%3E2577678724%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c273t-b81d93cb0b5abc534c15d5c04f4028ce8333db7d252a81d08970bdaf47f960cd3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2577678724&rft_id=info:pmid/&rfr_iscdi=true |