Odd chromatic number of graph classes

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F25%3A00380477" target="_blank" >RIV/68407700:21240/25:00380477 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1002/jgt.23200" target="_blank" >https://doi.org/10.1002/jgt.23200</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1002/jgt.23200" target="_blank" >10.1002/jgt.23200</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Odd chromatic number of graph classes

Popis výsledku v původním jazyce

A graph is called odd (respectively, even) if every vertex has odd (respectively, even) degree. Gallai proved that every graph can be partitioned into two even induced subgraphs, or into an odd and an even induced subgraph. We refer to a partition into odd subgraphs as an odd colouring of G $G$. Scott proved that a connected graph admits an odd colouring if and only if it has an even number of vertices. We say that a graph G $G$ is k $k$-odd colourable if it can be partitioned into at most k $k$ odd induced subgraphs. The odd chromatic number of G $G$, denoted by chi odd( G ) ${chi }_{text{odd}}(G)$, is the minimum integer k $k$ for which G $G$ is k $k$-odd colourable. We initiate the systematic study of odd colouring and odd chromatic number of graph classes. We first consider a question due to Scott, which states that every graph G $G$ of even order n $n$ has chi odd( G ) <= c n ${chi }_{text{odd}}(G)le csqrt{n}$, for some positive constant c $c$, by proving that this is indeed the case if G $G$ is restricted to having girth at least seven. We also show that any graph G $G$ whose all components have even order satisfies chi odd( G ) <= 2 Delta - 1 ${chi }_{text{odd}}(G)le 2{rm{Delta }}-1$, where Delta ${rm{Delta }}$ is the maximum degree of G $G$. Next, we show that certain interesting classes have bounded odd chromatic number. Our main results in this direction are that interval graphs, graphs of bounded modular-width all have bounded odd chromatic number. In particular, every even interval graph is 6-odd colourable, and every even graph is 3 m w $3mw$-odd colourable, where m w $mw$ is the modular width of a graph.

Název v anglickém jazyce

Odd chromatic number of graph classes

Popis výsledku anglicky

A graph is called odd (respectively, even) if every vertex has odd (respectively, even) degree. Gallai proved that every graph can be partitioned into two even induced subgraphs, or into an odd and an even induced subgraph. We refer to a partition into odd subgraphs as an odd colouring of G $G$. Scott proved that a connected graph admits an odd colouring if and only if it has an even number of vertices. We say that a graph G $G$ is k $k$-odd colourable if it can be partitioned into at most k $k$ odd induced subgraphs. The odd chromatic number of G $G$, denoted by chi odd( G ) ${chi }_{text{odd}}(G)$, is the minimum integer k $k$ for which G $G$ is k $k$-odd colourable. We initiate the systematic study of odd colouring and odd chromatic number of graph classes. We first consider a question due to Scott, which states that every graph G $G$ of even order n $n$ has chi odd( G ) <= c n ${chi }_{text{odd}}(G)le csqrt{n}$, for some positive constant c $c$, by proving that this is indeed the case if G $G$ is restricted to having girth at least seven. We also show that any graph G $G$ whose all components have even order satisfies chi odd( G ) <= 2 Delta - 1 ${chi }_{text{odd}}(G)le 2{rm{Delta }}-1$, where Delta ${rm{Delta }}$ is the maximum degree of G $G$. Next, we show that certain interesting classes have bounded odd chromatic number. Our main results in this direction are that interval graphs, graphs of bounded modular-width all have bounded odd chromatic number. In particular, every even interval graph is 6-odd colourable, and every even graph is 3 m w $3mw$-odd colourable, where m w $mw$ is the modular width of a graph.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Graph Theory

ISSN

0364-9024

e-ISSN

1097-0118

Svazek periodika

108

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

23

Strana od-do

722-744

Kód UT WoS článku

001357390600001

EID výsledku v databázi Scopus

2-s2.0-85208258355