Beyond degree choosability

MaRDI QIDQ2401410zbMATH OpenFDO

Authors Daniel W. Cranston, Landon Rabern

Publication date 8 September 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.00350, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p29

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

list coloringchoosabilityGallai treeAlon-Tarsi orientationdegree-choosable

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Abstract: Let $G$ be a connected graph with maximum degree $Delta$. Brooks' theorem states that $G$ has a $Delta$-coloring unless $G$ is a complete graph or an odd cycle. A graph $G$ is emph{degree-choosable} if $G$ can be properly colored from its lists whenever each vertex $v$ gets a list of $d(v)$ colors. In the context of list coloring, Brooks' theorem can be strengthened to the following. Every connected graph $G$ is degree-choosable unless each block of $G$ is a complete graph or an odd cycle; such a graph $G$ is a emph{Gallai tree}. This degree-choosability result was further strengthened to Alon--Tarsi orientations; these are orientations of $G$ in which the number of spanning Eulerian subgraphs with an even number of edges differs from the number with an odd number of edges. A graph $G$ is emph{degree-AT} if $G$ has an Alon--Tarsi orientation in which each vertex has indegree at least 1. Alon and Tarsi showed that if $G$ is degree-AT, then $G$ is also degree-choosable. Hladky, Kral, and Schauz showed that a connected graph is degree-AT if and only if it is not a Gallai tree. In this paper, we consider pairs $(G,x)$ where $G$ is a connected graph and $x$ is some specified vertex in $V(G)$. We characterize pairs such that $G$ has no Alon--Tarsi orientation in which each vertex has indegree at least 1 and $x$ has indegree at least 2. When $G$ is 2-connected, the characterization is simple to state.

Recommendations

• The colour theorems of Brooks and Gallai extended
• A note on graph coloring extensions and list-colorings
• Hypergraph extension of the Alon-Tarsi list coloring theorem
• On the Alon-Tarsi number and chromatic-choosability of Cartesian products of graphs
• Brooks' theorem via the Alon-Tarsi theorem

Cites work

• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3195967 (Why is no real title available?)
• A list version of Dirac's theorem on the number of edges in colour-critical graphs
• Brooks' theorem via the Alon-Tarsi theorem
• Color-critical graphs on a fixed surface
• Colorings and orientations of graphs
• Dirac's map-color theorem for choosability
• Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
• List colorings of \(K_5\)-minor-free graphs with special list assignments
• Mr. Paint and Mrs. Correct
• The last excluded case of Dirac's map‐color theorem for choosability

Cited in

(4)

• Degree Monotone Paths
• scientific article; zbMATH DE number 5354050 (Why is no real title available?)
• Comparatives Bring a Degree-Based NPI Licenser
• A hierarchy for cuppable degrees

This page was built for publication: Beyond degree choosability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2401410)