On P₅-Free Locally Split Graphs

[1] H. Ait Haddadene and H. Issaadi, Coloring perfect split neighbourhood graphs (CIRO 05’, 2005).Search in Google Scholar

[2] H. Ait Haddadene and H. Issaadi, Perfect graphs and vertex coloring problem, IAENG Int. J. Appl. Math. 39 (2009) 128–133.Search in Google Scholar

[3] V.E. Alekseev and V. Lozin, Independent sets of maximum weight in (p; q)-colorable graphs, Discrete Math. 265 (2003) 351–356. https://doi.org/10.1016/S0012-365X(02)00877-410.1016/S0012-365X(02)00877-4Search in Google Scholar

[4] A. Brandstädt, Partitions of graphs into one or two independent sets and cliques, Discrete Appl. Math. 152 (1996) 47–54. https://doi.org/10.1016/0012-365X(94)00296-U10.1016/0012-365X(94)00296-USearch in Google Scholar

[5] A. Brandstädt, (P₅, diamond)-free graphs revisited: structure and linear time optimization, Discrete Appl. Math. 138 (2004) 13–27. https://doi.org/10.1016/S0166-218X(03)00266-X10.1016/S0166-218X(03)00266-XSearch in Google Scholar

[6] A. Brandstädt and D. Kratsch, On the structure of (P₅, gem)-free graphs, Discrete Appl. Math. 145 (2005) 155–166. https://doi.org/10.1016/j.dam.2004.01.00910.1016/j.dam.2004.01.009Search in Google Scholar

[7] S. Brandt, Triangle-free graphs whose independence number equals the degree, Discrete Math. 310 (2010) 662–669. https://doi.org/10.1016/j.disc.2009.05.02110.1016/j.disc.2009.05.021Search in Google Scholar

[8] H.L. Bodlaender, A. Brandstädt, D. Kratsh, M. Rao and J. Spinrad, On algorithms for (P₅, gem)-free graphs, Theoret. Comput. Sci. 349 (2005) 2–21. https://doi.org/10.1016/j.tcs.2005.09.02610.1016/j.tcs.2005.09.026Search in Google Scholar

[9] F. Bonomo, M. Chudnovsky, P. Maceli, O. Schaudt, M. Stein and M. Zhong, 3-colouring graphs without triangles or induced paths on seven vertices (2014), submitted.Search in Google Scholar

[10] V. Chvátal, On certain polytopes associated with graphs, J. Combin. Theory Ser. B 18 (1975) 138–154. https://doi.org/10.1016/0095-8956(75)90041-610.1016/0095-8956(75)90041-6Search in Google Scholar

[11] D.G. Corneil, H. Lerchs and L. Stewart-Burlingham, Complement reducible graphs, Disrete Appl. Math. 3 (1981) 163–174. https://doi.org/10.1016/0166-218X(81)90013-510.1016/0166-218X(81)90013-5Search in Google Scholar

[12] D.G. Corneil, Y. Perl and L.K. Stewart, Cographs: recognition, applications and algorithms, Congr. Numer. 43 (1984) 249–258.Search in Google Scholar

[13] K. Dabrowski, V. Lozin, R. Raman and B. Ries, Colouring vertices of triangle-free graphs without forests, Discrete Math. 312 (2012) 1372–1385. https://doi.org/10.1016/j.disc.2011.12.01210.1016/j.disc.2011.12.012Search in Google Scholar

[14] Z. Dvořák and M. Mnich, Large independent sets in triangle-free planar graphs, Lecture Notes in Comput. Sci. 8737 (2014) 346–357. https://doi.org/10.1007/978-3-662-44777-2 2910.1007/978-3-662-44777-2Search in Google Scholar

[15] A. Frank, Some polynomial algorithms for certain graphs and hypergraphs, in: Proc. Fifth British Combinatorial Conf. Aberdeen 1975, C.Nash-Williams and J. Sheehan (Ed(s)), Congr. Numer. XV (1976) 211–226.Search in Google Scholar

[16] S. Földes and P.L. Hammer, Split graphs, in: 8th S-E Conf.on Combinatorics, Graph Theory and Computing, F. Hoffman et al. (Ed(s)), Congr. Numer. XIX (1977) 311–315.Search in Google Scholar

[17] T. Gallai, Transitiv orientatierbare graphen, Acta Math. Acad. Sci. Hungar. 18 (1967) 25–66. https://doi.org/10.1007/BF0202096110.1007/BF02020961Search in Google Scholar

[18] S. Gaspers, S. Haung and D. Paulusma, Colouring square-free graphs without long induced paths, J. Comput. System Sci. 106 (2019) 60–79. https://doi.org/10.1016/j.jcss.2019.06.00210.1016/j.jcss.2019.06.002Search in Google Scholar

[19] V. Giakoumakis and I. Rusu, Weighted parameters in (P₅, P¯5{\bar P_5}) graphs, Discrete Appl. Math. 80 (1997) 255–261. https://doi.org/10.1016/S0166-218X(97)00093-010.1016/S0166-218X(97)00093-0Search in Google Scholar

[20] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, 1980). https://doi.org/10.1016/C2013-0-10739-810.1016/C2013-0-10739-8Search in Google Scholar

[21] M. Habib and C. Paul, A survey of the algorithmic aspects of modular decomposition, Comput. Sci. Rev. 4 (2010) 41–59. https://doi.org/10.1016/j.cosrev.2010.01.00110.1016/j.cosrev.2010.01.001Search in Google Scholar

[22] P.L. Hammer and B. Simeone, The splittance of a graph, Combinatorica 1 (1981) 275–284. https://doi.org/10.1007/BF0257933310.1007/BF02579333Search in Google Scholar

[23] R. Hayward, C. Hoàng and F. Maffray, Optimizing weakly triangulated graphs, Graphs Combin. 5 (1989) 339–349. https://doi.org/10.1007/BF0178868910.1007/BF01788689Search in Google Scholar

[24] C C. Heckman and R. Thomas, Independent sets in triangle-free cubic planar graphs, J. Combin. Theory Ser. B 96 (2006) 253–275. https://doi.org/10.1016/j.jctb.2005.07.00910.1016/j.jctb.2005.07.009Search in Google Scholar

[25] C.T. Hoàng and B.A. Reed, Some classes of perfectly orderable graphs, J. Graph Theory 13 (1989) 445–463. https://doi.org/10.1002/jgt.319013040710.1002/jgt.3190130407Search in Google Scholar

[26] C.T. Hoàng, Efficient algorithms for minimum weighted colouring of some classes of perfect graphs, Discrete Appl. Math. 55 (1994) 133–143. https://doi.org/10.1016/0166-218X(94)90004-310.1016/0166-218X(94)90004-3Search in Google Scholar

[27] C.T. Hoàng, On the structure of (banner, odd hole)-free graphs, J. Graph Theory 89 (2018) 395–412. https://doi.org/10.1002/jgt.2225810.1002/jgt.22258Search in Google Scholar

[28] D. Lokshtanov, M. Vatshelle and Y. Villanger, Independent set in P₅-free graphs in polynomial time, in: Proc. of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, C. Chekuri (Ed(s)), (SIAM, 2014) 570–58. https://doi.org/10.1137/1.9781611973402.4310.1137/1.9781611973402.43Search in Google Scholar

[29] V. Lozin, J. Monnot and B. Ries, On the maximum independent set problem in subclasses of subcubic graphs, J. Discrete Algorithms 31 (2015) 104–112. https://doi.org/10.1016/j.jda.2014.08.00510.1016/j.jda.2014.08.005Search in Google Scholar

[30] F. Maffray and M. Preissmann, Linear recognition of pseudo-split graphs, Discrete Appl. Math. 52 (1994) 307–312. https://doi.org/10.1016/0166-218X(94)00022-010.1016/0166-218X(94)00022-0Search in Google Scholar

[31] N. Matsumoto and M. Tanaka, The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices, Aequationes Math. 95 (2021) 319–328. https://doi.org/10.1007/s00010-020-00760-z10.1007/s00010-020-00760-zSearch in Google Scholar

[32] C. McDiarmid and B.A. Reed, Channel assignment and weighted coloring, Networks 36 (2000) 114–117. https://doi.org/10.1002/1097-0037(200009)36:2¡114::AID-NET6¿3.0.CO;2-GSearch in Google Scholar

[33] R H. Möhring and F J. Radermacher, Substitution decomposition for discrete structures and connections with combinatorial optimization, North-Holland Math. Studies 95 (1984) 257–355. https://doi.org/10.1016/S0304-0208(08)72966-910.1016/S0304-0208(08)72966-9Search in Google Scholar

[34] M. Rao, Décompositions de Graphes et Algorithmes Efficaces, Ph.D. Thesis (Université Paul Verlaine, Metz, 2006).Search in Google Scholar

[35] P.D. Sumner, Graphs indecomposable with respet to the X-join, Discrete Math. 6 (1973) 281–298. https://doi.org/10.1016/0012-365X(73)90100-310.1016/0012-365X(73)90100-3Search in Google Scholar

• New Results on Type 2 Snarks¹

• Relationship among B1-EPG, VPT and EPT Graphs Classes

• Relaxed DP-Coloring and another Generalization of DP-Coloring on Planar Graphs without 4-Cycles and 7-Cycles

• Chorded k-Pancyclic and Weakly k-Pancyclic Graphs

• A Characterization of Internally 4-Connected {P₁₀ − {V₁, V₂}}-Minor-Free Graphs

• On s-Hamiltonian-Connected Line Graphs

• Enumerating the Digitally Convex Sets of Powers of Cycles and Cartesian Products of Paths and Complete Graphs

• New Bounds on Domination and Independence in Graphs¹

• Two Sufficient Conditions for Component Factors in Graphs

• The Turán Number of Spanning Star Forests

• Well-Covered Token Graphs

• On the Metric Dimensions for Sets of Vertices

• Beta Invariant and Chromatic Uniqueness of Wheels

• Hop Domination in Chordal Bipartite Graphs

• Cubic Graphs Having Only k-Cycles in Each 2-Factor

• Minimizing the Number of Complete Bipartite Graphs in a K_s-Saturated Graph

• Some Results on Path-Factor Critical Avoidable Graphs

• On a Graph Labelling Conjecture Involving Coloured Labels

• Double Total Dominator Chromatic Number of Graphs

• Graph Grabbing Game on Graphs with Forbidden Subgraphs

• Forbidden Subgraphs for Existences of (Connected) 2-Factors of a Graph

• On the Broadcast Independence Number of Locally Uniform 2-Lobsters

• The Hilton-Spencer Cycle Theorems Via Katona’s Shadow Intersection Theorem

• Cycles of Many Lengths in Balanced Bipartite Digraphs on Dominating and Dominated Degree Conditions

• Extending Potočnik and Šajna’s Conditions on the Existence of Vertex-Transitive Self-Complementary k-Hypergraphs

• On the Sizes of (k, l)-Edge-Maximal r-Uniform Hypergraphs

• A Note on the Upper Bounds on the Size of Bipartite and Tripartite 1-Embeddable Graphs on Surfaces

• Spanning Trees with a Bounded Number of Branch Vertices in a K_1,4-Free Graph

• Coalition Graphs of Paths, Cycles, and Trees

• A Characterization of Uniquely Representable Graphs

• Panchromatic Patterns By Paths

• On P₅-Free Locally Split Graphs

• Bounds on the Total Double Roman Domination Number of Graphs

• On the ρ-Subdivision Number of Graphs

• Scaffold for the Polyhedral Embedding of Cubic Graphs

• The Linear Arboricity of Graphs with Low Treewidth

• Vertex-Edge Domination in Interval and Bipartite Permutation Graphs

• Domination Game: Effect of Edge Contraction and Edge Subdivision

• The Decycling Number of a Planar Graph Covered By K₄-Subgraphs

• On Q-Connected Chordal Graphs with Minimum Number of Spanning Trees

• Degree Sum Condition for Vertex-Disjoint 5-Cycles

• Strong and Weak Perfect Digraph Theorems for Perfect, α-Perfect and Strictly Perfect Digraphs

• L(2, 1)-Labeling of the Iterated Mycielski Graphs of Graphs and Some Problems Related to Matching Problems

• About an Extremal Problem of Bigraphic Pairs with a Realization Containing K_s,t¹

• On the Equality of Domination Number and 2-Domination Number

• Optimal Error-Detecting Open-Locating-Dominating Set on the Infinite Triangular Grid

• The Achromatic Number of the Cartesian Product of K₆ and K_q

• The Graph Grabbing Game on Blow-ups of Trees and Cycles

• A Note on Forcing 3-Repetitions in Degree Sequences

• Linear Arboricity of 1-Planar Graphs

• Vertex Partitioning of Graphs Into Odd Induced Subgraphs

• On the Ramsey Numbers of Non-Star Trees Versus Connected Graphs of Order Six

• Daisy Hamming Graphs

• Edge Degree Conditions for Dominating and Spanning Closed Trails

• Strengthening Some Complexity Results on Toughness of Graphs

• Unique Minimum Semipaired Dominating Sets in Trees

• Extremal Graphs for Even Linear Forests in Bipartite Graphs

• ℓ-Covering k-Hypergraphs are Quasi-Eulerian

• Zero and Total Forcing Dense Graphs

• On Conditional Connectivity of the Cartesian Product of Cycles

• The Walks and CDC of Graphs with the Same Main Eigenspace

• Burnside Chromatic Polynomials of Group-Invariant Graphs

• Total and Paired Domination Stability in Prisms

• Generalized Turán Problems for Small Graphs

• The Achromatic Number of K₆ □ K_q Equals 2q + 3 If q ≥ 41 is Odd

• Total 2-Domination Number in Digraphs and Its Dual Parameter

• Metric Dimension and Diameter in Bipartite Graphs

• A Decomposition for Digraphs with Minimum Outdegree 3 Having No Vertex Disjoint Cycles of Different Lengths

• On Semi-Transitive Orientability of Triangle-Free Graphs

• Countable Graphs Are Majority 3-Choosable

• Identifying Codes in the Direct Product of a Path and a Complete Graph

• Determining Number and Cost of Generalized Mycielskian Graphs

• Set-Sequential Labelings of Odd Trees

• Lower Boundary Independent Broadcasts in Trees

• Improved Bounds for Some Facially Constrained Colorings

• Minimal Graphs with Disjoint Dominating and Total Dominating Sets

• Equimatchable Bipartite Graphs

• The Threshold Dimension and Irreducible Graphs

• Edge Intersection Hypergraphs

• More Tales of Hoffman: Bounds for the Vector Chromatic Number of a Graph

• On Distance Magic Labelings of Hamming Graphs and Folded Hypercubes

• An Upper Bound on the Chromatic Number of 2-Planar Graphs

• The Existence of Path-Factor Covered Graphs

• On Subgraphs with Prescribed Eccentricities

• Domination Parameters of the Unitary Cayley Graph of 𝕑/n𝕑

• Double Roman and Double Italian Domination

• An Improved Bound on the Chromatic Number of the Pancake Graphs

• Efficient (j, k)-Dominating Functions

• Elimination Properties for Minimal Dominating Sets of Graphs

• Choosability with Separation of Cycles and Outerplanar Graphs

• The Neighbor-Locating-Chromatic Number of Trees and Unicyclic Graphs

• Edge-Maximal Graphs with Cutwidth at Most Three

• The Petersen and Heawood Graphs Make Up Graphical Twins Via Induced Matchings

• A Note About Monochromatic Components in Graphs of Large Minimum Degree