Coloring minimal Cayley graphs.
In 1978 Babai raised the question whether all minimal Cayley graphs have bounded chromatic number; in 1994 he conjectured a negative answer. In this paper we show that any minimal Cayley graph of a (finitely generated) generalized dihedral or nilpotent group has chromatic number at most 3, while 4 c...
| Authors: | ; |
|---|---|
| Format: | Article |
| Status: | Published version |
| Publication date: | 2025 |
| Country: | España |
| Institution: | Varias* (Consorci de Biblioteques Universitáries de Catalunya, Centre de Serveis Científics i Acadèmics de Catalunya) |
| Repository: | Recercat. Dipósit de la Recerca de Catalunya |
| OAI Identifier: | oai:recercat.cat:2445/224639 |
| Online Access: | https://hdl.handle.net/2445/224639 |
| Access Level: | Open access |
| Keyword: | Teoria de grafs Geometria combinatòria Graph theory Combinatorial geometry |
| _version_ | 1878735044901601280 |
|---|---|
| author | García Marco, Ignacio |
| author2 | Knauer, Kolja |
| author2_role | author |
| author_browse | García Marco, Ignacio Knauer, Kolja |
| author_facet | García Marco, Ignacio Knauer, Kolja |
| author_role | author |
| collection | Recercat. Dipósit de la Recerca de Catalunya |
| description | In 1978 Babai raised the question whether all minimal Cayley graphs have bounded chromatic number; in 1994 he conjectured a negative answer. In this paper we show that any minimal Cayley graph of a (finitely generated) generalized dihedral or nilpotent group has chromatic number at most 3, while 4 colors are sometimes necessary for soluble groups. On the other hand we address a related question proposed by Babai in 1978 by constructing graphs of unbounded chromatic number that admit a proper edge coloring such that each cycle has some color at least twice. The latter can be viewed as a step towards confirming Babai’s 1994 conjecture – a problem that remains open. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | ES_74d5bfa9cbc0c6e5ff5e5a2f3ddfa8cd |
| institution | Varias* (Consorci de Biblioteques Universitáries de Catalunya, Centre de Serveis Científics i Acadèmics de Catalunya) |
| instname_str | Varias* (Consorci de Biblioteques Universitáries de Catalunya, Centre de Serveis Científics i Acadèmics de Catalunya) |
| network_acronym_str | ES |
| network_name_str | España |
| oai_identifier_str | oai:recercat.cat:2445/224639 |
| publishDate | 2025 |
| publishDateSort | 2025 |
| publisher | Elsevier Ltd. |
| publisherStr | Elsevier Ltd. |
| reponame_str | Recercat. Dipósit de la Recerca de Catalunya |
| spelling | Coloring minimal Cayley graphs. García Marco, Ignacio Knauer, Kolja Teoria de grafs Geometria combinatòria Graph theory Combinatorial geometry In 1978 Babai raised the question whether all minimal Cayley graphs have bounded chromatic number; in 1994 he conjectured a negative answer. In this paper we show that any minimal Cayley graph of a (finitely generated) generalized dihedral or nilpotent group has chromatic number at most 3, while 4 colors are sometimes necessary for soluble groups. On the other hand we address a related question proposed by Babai in 1978 by constructing graphs of unbounded chromatic number that admit a proper edge coloring such that each cycle has some color at least twice. The latter can be viewed as a step towards confirming Babai’s 1994 conjecture – a problem that remains open. Elsevier Ltd. https://hdl.handle.net/2445/224639 |
| spellingShingle | Coloring minimal Cayley graphs. García Marco, Ignacio Teoria de grafs Geometria combinatòria Graph theory Combinatorial geometry |
| status_str | publishedVersion |
| title | Coloring minimal Cayley graphs. |
| title_full | Coloring minimal Cayley graphs. |
| title_fullStr | Coloring minimal Cayley graphs. |
| title_full_unstemmed | Coloring minimal Cayley graphs. |
| title_short | Coloring minimal Cayley graphs. |
| title_sort | Coloring minimal Cayley graphs. |
| topic | Teoria de grafs Geometria combinatòria Graph theory Combinatorial geometry |
| topic_facet | Teoria de grafs Geometria combinatòria Graph theory Combinatorial geometry |
| url | https://hdl.handle.net/2445/224639 |