BROWSE

Related Scientist

janecook,linda's photo.

janecook,linda
이산수학그룹
more info

ITEM VIEW & DOWNLOAD

Proving a Directed Analog of the Gyarfas-Sumner Conjecture for Orientations of P4

Cited 0 time in webofscience Cited 0 time in scopus
52 Viewed 0 Downloaded
Title
Proving a Directed Analog of the Gyarfas-Sumner Conjecture for Orientations of <i>P</i><sub>4</sub>
Author(s)
Linda Cook; Masarik, Tomas; Pilipczuk, Marcin; Amadeus Reinald; Souza, Ueverton S.
Publication Date
2023-09
Journal
Electronic Journal of Combinatorics, v.30, no.3
Publisher
Electronic Journal of Combinatorics
Abstract
An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph D is H-free if D does not contain H as an induced sub(di)graph. The Gyarfas-Sumner conjecture is a widely-open conjecture on simple graphs, which states that for any forest F, there is some function f such that every F-free graph G with clique number omega(G) has chromatic number at most f(omega(G)). Aboulker, Charbit, and Naserasr [Extension of Gyarfas-Sumner Conjecture to Digraphs, Electron. J. Comb., 2021] proposed an analog of this conjecture to the dichromatic number of oriented graphs. The dichromatic number of a digraph D is the minimum number of colors required to color the vertex set of D so that no directed cycle in D is monochromatic.Aboulker, Charbit, and Naserasr's ->-chi-boundedness conjecture states that for every oriented forest F, there is some function f such that every F-free oriented graph D has dichromatic number at most f(omega(D)), where omega (D) is the size of a maximum clique in the graph underlying D. In this paper, we perform the first step towards proving Aboulker, Charbit, and Naserasr's ->-chi-boundedness conjecture by showing that it holds when F is any orientation of a path on four vertices.Mathematics Subject Classifications: 05C88, 05C89
URI
https://pr.ibs.re.kr/handle/8788114/14632
DOI
10.37236/11538
ISSN
1077-8926
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > 1. Journal Papers (저널논문)
Files in This Item:
There are no files associated with this item.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse