The interleaved multichromatic number of a graph

DOI10.1007/S000260200001MaRDI QIDQ1400779zbMATH OpenOpenAlexFDO

Authors Valmir C. Barbosa

Publication date 14 August 2003

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0309380

zbMATH Keywords

acyclic orientationschromatic numberinterleaved multichromatic numbermultichromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: For $kge1$, we consider interleaved $k$-tuple colorings of the nodes of a graph, that is, assignments of $k$ distinct natural numbers to each node in such a way that nodes that are connected by an edge receive numbers that are strictly alternating between them with respect to the relation $<$. If it takes at least $ch{i}_{int}^k(G)$ distinct numbers to provide graph $G$ with such a coloring, then the interleaved multichromatic number of $G$ is $ch{i}_{int}^{\ast }(G)=in{f}_{kge1}ch{i}_{int}^k(G)/k$ and is known to be given by a function of the simple cycles of $G$ under acyclic orientations if $G$ is connected [1]. This paper contains a new proof of this result. Unlike the original proof, the new proof makes no assumptions on the connectedness of $G$, nor does it resort to the possible applications of interleaved $k$-tuple colorings and their properties.

Recommendations

• Interleaved adjoints of directed graphs
• On the chromatic number of a subgraph of the Kneser graph
• Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs
• scientific article; zbMATH DE number 2097444
• A note on graph colouring

Cited in

(4)

• On the chromatic number of multiple interval graphs and overlap graphs
• Resource-sharing system scheduling and circular chromatic number
• Resource-sharing systems and hypergraph colorings
• Interleaved adjoints of directed graphs

This page was built for publication: The interleaved multichromatic number of a graph

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