ISGCI References 1500 - 1599
Note: The references are not ordered
alphabetically!
1500
K3,3 is a discriminating graph.
1501
G. Duran, M.C. Lin
Clique graphs of Helly circular-arc graphs
Ars Combin. 60 255-271 (2001)
1502
G. Duran, M.C. Lin
On some subclasses of circular-arc graphs
Technical Report TR003-99 Departamento de Computacion, FCEyN, Universided de Buenos Aires (1999)
1503
B. Hedman
Clique graphs of time graphs
J. Combin. Theory Ser. B. 37 (3) 270-278 (1968)
1504
For any graph G, if we add a universal vertex vertex v, G+v is a dually chordal graph. This fact allows a trivial reduction,
since the new vertex increases the chromatic number and the size of the largest clique by exactly 1. (Communicated by Vinicius
Santos)
Furthermore, the clique cover number of G and G+v are equal, hence we have a reduction for clique cover, as well. (Communicated
by Arne Leitert)
1505
A. Leitert
3-Colourability of dually chordal graphs in linear time
Manuscript, 2012
Available on
arxiv.
1506
For any connected graph G, if we add a universal vertex vertex v, H = G+v is a locally connected graph. This fact allows a
trivial reduction, since the new vertex increases the chromatic number and the size of the largest clique by exactly 1. Furthermore,
the clique cover number of G and G+v are equal, hence we have a reduction for clique cover, as well. Similarly for independent
set. (Communicated by Pavel Irzhavski). Treewidth is reduced analogously to clique (Communicated by Arne Leitert). For the
domination problem, we add a true twin to every vertex (V*={v, v* | v in V} and E*={uv, u*v, uv*, u*v* | uv in E}). Then
every dominating set in G is also dominating in G* and a minimal dominating set in G* can be converted to a minimal dominating
set in G by replacing every vertex v* in the set by v (Communicated by Arne Leitert).
1507
P. Heggernes, P. van 't Hof, D. Lokshtanov, J. Nederlof
Computing the cutwidth of bipartite permutation graphs in linear time
Proceedings of the 36th international conference on Graph-theoretic concepts in computer science WG 2010 75-87 (2010)
Available
here.
1508
D.M. Thilikos, M. Serna, H.L. Bodlaender
Cutwidth I: a linear time fixed parameter algorithm
J. of Algorithms 56 Issue 1 1-24 (2005)
1509
B. Monien, I.H. Sudborough
Min cut is NP-complete for edge weighted trees
Theoretical Comp. Sci. 58 Issue 1-3, 209-229 (1988)
1510
P. Heggernes, D. Lokshtanov, R. Mihai, C. Papadopoulos
Cutwidth of split graphs, threshold graphs, and proper interval graphs
Proceedings of WG 2008, LNCS 5344, pp. 218-229 (2008)
1511
J. Diaz, M. Penrose, J. Petit, M. Serna
Approximating layout problems on random geometric graphs
Journal of Algorithms 39 78-117 (2001)
1512
J. Diaz, J. Petit, M. Serna
A survey on graph layout problems
ACM Computing surveys 34 313-356 (2002)
1513
J. Yuan, S. Zhou
Optimal labelling of unit interval graphs
Appl. Math. J. Chinese Univ. Ser. B (English edition) 10 337-344 (1995)
1514
M. Yannakakis
A polynomial algorithm for the min cut linear arrangement of trees
Journal of ACM Vol 32, 950-988 (1985)
1515
D.M. Thilikos, M. Serna, H.L. Bodlaender
Cutwidth II: algorithms for partial w-trees of bounded degree
J. of Algorithms 56 Issue 1 25-49 (2005)
1516
H. ElGindy
Hierarchical decomposition of polygons with applications
Ph.D. Thesis, McGill University (1985)
1519
G. Narasimhan
A note on the Hamiltonian Circuit Problem on directed path graphs
Information Proc. Lett. 32 No.4 167-170 (1989)
doi 10.1016/0020-0190(89)90038-0
1520
A.A. Bertossi, M.A. Bonuccelli
Hamiltonian Circuits in interval graph generalizations
Information Proc. Lett. 23 195-200 (1986)
1521
A.A. Bertossi
The edge Hamiltonian path problem is NP-complete
Information Proc. Lett. 13 157-159 (1981)
1522
T.-H. Lai, S.-S. Wei
The edge Hamiltonian path problem is NP-complete for bipartite graphs
Information Proc. Lett. 46 No.1 21-26 (1993)
1523
T. Akiyama, T. Nishizeki, N. Saito
NP-completeness of the Hamiltonian cycle problem for bipartite graphs
J. Inf. Process. V.3 73-76 (1980)
1524
J.S. Deogun, G. Steiner
Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
SIAM J. Computing 23 Issue 3 520-552 (1994)
doi 10.1137/S0097539791200375
1525
C.J. Colbourn, L.K. Stewart
Dominating cycles in series-parallel graphs
Ars Combin. 19A 107-112 (1985)
1526
B.S. Panda, D. Pradhan
NP-Completeness of Hamiltonian Cycle Problem on Rooted Directed Path Graphs
Manuscript
Available on
arXiv.
1527
W.K. Shih, T.C. Chen, W.L. Hsu
An O(n^2 log n) algorithm for the Hamiltonian cycle problem on circular-arc graphs
SIAM J. Comput. 21 No.6 1026-1046 (1992)
1528
L. Ibarra
A simple algorithm to find Hamiltonian cycles in proper interval graphs
Information Proc. Lett. 109 Issue 18 1105-1108 (2009)
1529
J.M. Keil
Finding hamiltonian circuits in interval graphs
Information Proc. Lett. 20 201-206 (1985)
1530
B.S. Panda, S.K. Das
A linear time recognition algorithm for proper interval graphs
Information Proc. Lett. 87 153-161 (2003)
1531
A.A. Bertossi
Finding hamiltonian circuits in proper interval graphs
Information Proc. Lett. 17 97-101 (1983)
1532
G.K. Manacher, T.A. Mankus, C.J. Smith
An optimum θ(n log n) algorithm for finding a canonical hamiltonian path and a canonical hamiltonian circuit in a set of intervals
Information Proc. Lett. 35 205-211 (1990)
1533
M.S. Krisnamoorthy
An NP-hard problem in bipartite graphs
SIGACT News 7 26-26 (1976)
1534
R.W. Hung, M.S. Chang
Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
Theoret. Comput. Sci. 341 411-440 (2005)
1535
S.Y. Hsieh, C.W. Ho, T.S. Hsu, M.T. Ko
The Hamiltonian problem on distance-hereditary graphs
Discrete Appl. Math. 153 508-524 (2006)
1536
R.-W. Hung, M.-S. Chang, C.-H. Laio
The Hamiltonian cycle problem on circular-arc graphs
Proc. of the International MultiConference of Engineers and Computer Scientists IMECS 2009
1537
A. Itai, C. H. Papadimitriou, J. L. Szwarcfiter
Hamiltonian paths in grid graphs
SIAM J. Comput. Vol.11 No.4 676-686 (1982)
1538
C. Umans, W. Lenhart
Hamiltonian cycles in solid grid graphs
Proc. of Foundations in Comp. Sci. FOCS 1997 496-505 (1997)
1539
M.R. Garey, D.S. Johnson, R.E. Tarjan
The planar Hamiltonian circuit problem is NP-complete
SIAM J. Comput. Vol.5 704-714 (1976)
1540
V.I. Benediktovich, V.I. Sarvanov
Hamiltonian cycle problem for planar cubic graphs
Doklady of the academy of sciences of Belarus No.1 34-37 (1997)
1541
Hamiltonian cycle is NP-complete for locally connected graphs. Add a universal vertex u to a graph G. G has a Hamiltonian
path if and only if G+u has a Hamiltonian cycle.
=>: G has a Hamiltonian path with starting vertex s and ending vertex e. Thus, (s, ..., e, u, s) is a Hamiltonian cycle in
G+u.
<=: G+u has a Hamiltonian cycle. Therefore u has two neighbours s and e in the cycle. Thus (s, ..., e) is a Hamiltonian path
in G. (Communicated by Arne Leitert, Pavel Irzhavski)
1542
H. Sachs
Über selbstkomplementäre Graphen
Publ. Math. Debrecen 9 270-288 (1962)
1543
G.B. Mertzios, I. Bezakova
Computing and counting longest paths on circular-arc graphs in polynomial time
Discrete Appl. Math, in press
doi 10.1016/j.dam.2012年08月02日4
1544
It is well known that the tree-width of a chordal graph is one less
than its maximal clique. It is also well known that a planer graph can
not have any clique of size 5 or greater, hence chordal \cap planar has
treewidth at most 3 (Communicated by Vatshelle)
1545
A. Asinowski, E. Cohen, M.C. Golumbic, V. Limouzy, M. Lipshteyn, M. Stern
Vertex intersection graphs of paths on a grid
Journal of Graph Algorithms and Applications Vol.16 No.2 129-150 (2012)
1546
M. Middendorf, F. Pfeiffer
The max clique problem in classes of string-graphs
Discrete Math. 108 365-372 (1992)
1547
K. Appel, W. Haken
Every planar map is four colorable Part I. Discharging
Illinois J. of Math. 21 429-490 (1977)
1548
K. Appel, W. Haken
Every planar map is four colorable Part II. Reducibility
Illinois J. of Math. 21 491-567 (1977)
1549
K. Appel, W. Haken
Every planar map is four-colorable
American Mathematical Society (1989)
1550
F. Gurski
Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
Discrete Math. 306 No.2 271-277 (2006)
doi 10.1016/j.disc.2005年11月01日4
1551
D. Eppstein described this class in an
answer to a question of Y. Cao.
1552
A. Butman, D. Hermelin, M. Lewenstein, D. Rawitz
Optimization problems in multiple-interval graphs
Proc. of 17th annual ACM-SIAM symposium on Discrete algorithms SODA2007 268-277 (2007)
1553
M.C. Francis, D. Goncalves, P. Ochem
The maximum clique problem in multiple interval graphs
Proceedings of WG 2012, Lecture Notes in Computer Science 7551, 57-68 (2012)
1554
F. Koenig
Sorting with objectives
Ph.D. thesis, Technische Universitaet Berlin (2009)
1555
V.S. Gordon, Y.L. Orlovich, C.N. Potts, V.A. Strusevich
Hamiltonian properties of locally connected graphs with bounded vertex degree
Discrete Appl. Math. 159 1759-1774 (2011)
1556
G. Chartrand, R. Pippert
Locally connected graphs
Casopis Pest. M at. 99 158-163 (1974)
1557
A. Abueida, R. Sritharan
Cycle extendability and hamiltonian cycles in chordal graph classes
SIAM J. Discrete Math. 20 669-681 (2006)
1558
T. Jiang
Planar Hamiltonian chordal graphs are cycle extendable
Discrete Math. 257 441-444 (2002)
1559
G.R.T. Hendry
Extending cycles in graphs
Discrete Math. 85 59-72 (1990)
1561
D. Tankus, M. Tarsi
The structure of well-covered graphs and the complexity of their recognition problems
J. Combin. Th. Series B 69 No.2 230-233 (1997)
doi 10.1006/jctb.1996.1742
1563
M. Lesk, M.D. Plummer, W.R. Pulleyblank
Equi-matchable graphs
Graph theory and combinatorics (Cambridge, 1983), 239–254, Academic Press, London, 1984
1564
M.D. Plummer
Well-covered graphs: A survey
Quaestiones Math. 16 No.3 253-287
1565
E.M. Arkin, S.P. Fekete, K. Islam, H. Meijer, J.S.B. Mitchell, Y. Nunez-Rodriguez, V. Polishchuk, D. Rappaport, H. Xiao
A study of grid hamiltonicity: Not being (super)thin or solid is hard
Computational Geometry: Theory and Applications 42 No.6-7 582-605 (2009)
1566
V.S. Gordon, Y.L. Orlovich, F. Werner
Hamiltonian properties of triangular grid graphs
Discrete Math. 308 6166-6188 (2008)
1567
D.J. Oberly, S.K. Simic, D.P. Sumner
Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
J. Graph Th. Vol.3 No.4 351-356 (1979)
1568
J.R. Reay, T. Zamfirescu
Hamiltonian cycles in T-graphs
Discrete Comput. Geom. 24 497-502 (2000)
1569
Yu.L. Orlovich
On locally connected graphs whose maximal vertex degree is at most four
Vestsi Nats. Akad. Navuk Belarusi. Ser. Fiz.-Mat. Navuk No.3 97-100 (1999)
1571
M. de Berg, O. Cheong, M. van Kreveld, M. Overmars
Computation geometry: Algorithms and applications
Springer Verlag (2008)
1572
T. Hiroshima, Y. Miyamoto, K. Sugihara
Computation geometry: Algorithms and applications
IEICE Trans. Fundamentals Vol. E83 A, No.4 627-638 (2000)
1573
D.E. Taylor, R. Levingston
Distance-regular graphs
Proceedings of the International Conference on Combinatorial Theory, Lecture Notes in Mathematics 686, 313–323 (1978)
1574
P. Festa, P.M. Pardalos, M.G.C. Resende
Feedback set problems
in: D.Z. Du, P.M. Pardalos, Handbook of Combinatorial Optimization, Supplement vol. A, Kluwer Academic Publishers, 209-259
(2000)
1575
A. Brandstaedt
On improved time bounds for permutation graph problems
Intern. Workshop on Graph--Theoretic Concepts in Comp. Sci. 1993, Lecture Notes in Comp. Sci. 657 1-10 (1993)
1577
C.L. Lu, C.Y. Tang
A linear-time algorithm for the weighted feedback vertex problem on interval graphs
Information Proc. Lett. 61 107-111 (1997)
1578
S.R. Coorg, C.P. Rangan
Feedback vertex set on cocomparability graphs
Networks 26 101-111 (1995)
1579
M.S Chang, Y.D. Liang
Minimum feedback vertex set in cocomparability graphs and convex bipartite graphs
Acta Informatica 34 337-346 (1997)
1580
C. Wang, T. Liu, W. Jian, K. Xu
Feedback vertex set on tree convex bipartite graphs
Proceedings of COCOA 2012 LNCS 7402 95-102 (2012)
1581
Feedback vertex set on AT-free graphs
D. Kratsch, H. Mueller, I. Todinca
Discrete Appl. Math. 156 No. 10 1936-1947 (2008)
doi 10.1016/j.dam.200710006
1582
B. Courcelle, S. Oum
Vertex-minors, monadic second-order logic and a conjecture by Seese
J. Comb. Theory (B) 97 91-126 (2007)
1583
T. Kloks, C.-H. Liu, S.-H. Poon
Feedback vertex set on chordal bipartite graphs
Manuscript (2012)
Available on
arXiv.
1584
A. Takaoka, S. Tayu, S. Ueno
On minimum feedback vertex set in graphs
Third Internation Conference on Networking and Computing 429-434 (2012)
doi 10.1109/ICNC.2012.81
1585
F. Gavril
Minimum weight feedback vertex sets in circle graphs
Information Proc. Lett. 107 No.1 1-6 (2008)
doi 10.1016/j.ipl.200712003
1586
S. Ueno, Y. Kajitani, S. Gotoh
On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
Discrete Math. 72 No.1-3 355-360 (1988)
doi 10.1016/0012-365X(88)90226-9
1587
D. Li, Y. Liu,
A polynomial algorithm for finding the minimum feedback vertex set of a 3-regular simple graph
Acta Math. Sci. (English Ed.) 19 (1999), no. 4, 375–381
1588
The decycling number of graphs
S. Bau, L.W. Beineke
Australas. J. Comb. 25 285-298 (2002)
1589
R.M. Karp
Reducibility among combinatorial problems
Complexity of Computer Computations (R.E. Miller, J.W. Thatcher, ed.), Plenum Press, New York-London 85-103 (1972)
1590
W. Jiang, T. Liu, T. Ren, K. Xu
Two hardness results on feedback vertex sets
Frontiers in Algorithmics and Algorithmic Aspects in Information and Management; Lecture Notes in Computer Science 6681 233-243
(2011)
1591
W. Jiang, T. Liu, K. Xu
Tractable feedback vertex sets in restricted bipartite graphs
Proceedings of COCOA 2011 Lecture Notes in Computer Science 6831, 424-434 (2011)
1592
E. Speckenmeyer
On feedback vertex sets and nonseparating independent sets in cubic graphs
J. of Graph Theory 12 No.3 405-412 (1988)
doi 10.1002/jgt.3190120311
1593
Feedback vertex set is NP-complete for planar graph of maximum degree 4. By subdividing each edge by one new vertex, it easily
follows that feedback vertex set is also NP-complete on bipartite planar graphs of maximum degree 4 (V.B. Le).
1594
J.M. Keil, L. Stewart
Approximating the minimum cover and other hard problems in subtree filament graphs
Discrete Appl. Math. 154 1983-1995 (2006)
1595
F. Gavril
Minimum weight feedback vertex sets in circle n-gon graphs and circle trapezoid graph
Discrete Math. Algorithm. Appl. 3, 323-336 (2011)
doi 10.1142/S1793830911001243
1596
Y.-L. Lin
Circular and circle trapezoid graphs
J. Sci. Eng. Tech. 2 11-17 (2006)
1597
D. Kratsch, T. Kloks, H. Mueller
Measuring the vulnerability for classes of intersection graphs
Discrete Appl. Math. 77 259-270 (1997)
1598
M.M. Halldorson, S. Kitaev, A. Pyatkin
Alternation graphs
Proceedings of WG 2011, Lecture Notes in Computer Science 6986, 191-202 (2011)
1599
S. Kitaev, A. Pyatkin
On representable graphs
Automata, languages and Combinatorics 13 No.1 45-54 (2008)